package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tzp
 * @since 2020/9/11
 */
public class TreeNode implements TreeProblem {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }

    public static TreeNode depre(Integer[] a) {
        List<TreeNode> cache = new ArrayList<>(a.length);
        for (int i = 0; i < a.length; i++) {
            if (a[i] != null) {
                TreeNode ni = new TreeNode(a[i]);
                cache.add(ni);
                if (i != 0) {
//                    int level = (int) (Math.log(i + 1) / Math.log(2) + 1);
                    int parent = (int) Math.floor((i + 1) / 2.0) - 1;
                    if (cache.get(parent) == null) {
                        System.out.println("xx");
                    }
                    if (cache.get(parent).left != null) {
                        cache.get(parent).left = ni;
                    } else {
                        cache.get(parent).right = ni;
                    }

                }
            } else {
                cache.add(null);
            }
        }
        return cache.get(0);
    }

    /**
     * 重点关注
     * 有特么那么难????
     */
    public static TreeNode arrayToTreeNode(Integer[] a) {
        List<TreeNode> cache = new ArrayList<>(a.length);
        TreeNode root = new TreeNode(a[0]);
        cache.add(root);
        int parentLNum = 1;//父级那一层非空节点数
        int parentStart = 0;
        for (int i = 1; i < a.length; ) {//i=本层start
            int currentLNum = 0;//本级那一层非空节点数
            for (int j = 0; j < parentLNum; j++) {
                if (i + 2 * j < a.length) {
                    Integer l = a[i + 2 * j];
                    if (l != null) {
                        currentLNum++;
                        TreeNode nl = new TreeNode(l);
                        cache.get(parentStart + j).left = nl;
                        cache.add(nl);
                    }
                }
                if (i + 2 * j + 1 < a.length) {
                    Integer r = a[i + 2 * j + 1];
                    if (r != null) {
                        currentLNum++;
                        TreeNode nr = new TreeNode(r);
                        cache.get(parentStart + j).right = nr;
                        cache.add(nr);
                    }
                }
            }
            i = i + 2 * parentLNum;
            parentStart += parentLNum;
            parentLNum = currentLNum;
        }
        return root;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 4, 3, 5, 7, 10, 6, null, 8, null, 11, 9, 15, null, null, null, 12, null, null, null, 13, null, null, null, null, 14};
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);
        System.out.println(treeNode);

//        System.out.println(Math.log(1) + 1);
    }
}